// queue standard header -*-c++-*-
// Copyright 2003-2010 IAR Systems AB. 
#ifndef _QUEUE_
#define _QUEUE_

#ifndef _SYSTEM_BUILD
#pragma system_include
#endif

#include <algorithm>
#include <deque>
#include <functional>
#include <vector>
_STD_BEGIN

#pragma language = save
#pragma language = extended
// TEMPLATE CLASS queue
template<class _Ty,
         class _Container = deque<_Ty> >
class __memory_of(_Ty) queue
{       // FIFO queue implemented with a container
public:
  typedef _Container container_type;
  typedef typename _Container::value_type value_type;
  typedef typename _Container::size_type size_type;
  typedef typename _TypeUtil::_ParameterType<value_type>::_Type _ParamTy;

  queue()
    : c()
  {}      // construct with empty container

  explicit queue(const _Container& _Cont)
    : c(_Cont)
  {}      // construct by copying specified container

  bool empty() const
  {       // test if queue is empty
    return (c.empty()); 
  }

  size_type size() const
  {       // return length of queue
    return (c.size()); 
  }

  value_type& front()
  {       // return first element of mutable queue
    return (c.front()); 
  }

  const value_type& front() const
  {       // return first element of nonmutable queue
    return (c.front()); 
  }

  value_type& back()
  {       // return last element of mutable queue
    return (c.back()); 
  }

  const value_type& back() const
  {       // return last element of nonmutable queue
    return (c.back()); 
  }

  void push(_ParamTy _Val)
  {       // insert element at beginning
    c.push_back(_Val); 
  }

  void pop()
  {       // erase element at end
    c.pop_front(); 
  }

//protected:
  _Container c;   // the underlying container
};

// queue TEMPLATE FUNCTIONS
template<class _Ty,
         class _Container> inline
bool operator==(const queue<_Ty, _Container>& _Left,
                const queue<_Ty, _Container>& _Right)
{       // test for queue equality
  return (_Left.c == _Right.c); 
}

template<class _Ty,
         class _Container> inline
bool operator!=(const queue<_Ty, _Container>& _Left,
                const queue<_Ty, _Container>& _Right)
{       // test for queue inequality
  return (!(_Left == _Right)); 
}

template<class _Ty,
         class _Container> inline
bool operator<(const queue<_Ty, _Container>& _Left,
               const queue<_Ty, _Container>& _Right)
{       // test if _Left < _Right for queues
  return (_Left.c < _Right.c); 
}

template<class _Ty,
         class _Container> inline
bool operator>(const queue<_Ty, _Container>& _Left,
               const queue<_Ty, _Container>& _Right)
{       // test if _Left > _Right for queues
  return (_Right < _Left); 
}

template<class _Ty,
         class _Container> inline
bool operator<=(const queue<_Ty, _Container>& _Left,
                const queue<_Ty, _Container>& _Right)
{       // test if _Left <= _Right for queues
  return (!(_Right < _Left)); 
}

template<class _Ty,
         class _Container> inline
bool operator>=(const queue<_Ty, _Container>& _Left,
                const queue<_Ty, _Container>& _Right)
{       // test if _Left >= _Right for queues
  return (!(_Left < _Right)); 
}

// TEMPLATE CLASS priority_queue
template<class _Ty,
         class _Container = vector<_Ty>,
         class _Pr = less<typename _Container::value_type> >
class __memory_of(_Ty) priority_queue
{       // priority queue implemented with a _Container
public:
  typedef _Container container_type;
  typedef typename _Container::value_type value_type;
  typedef typename _Container::size_type size_type;
  typedef typename _TypeUtil::_ParameterType<value_type>::_Type _ParamTy;

  priority_queue()
    : c(), comp()
  {}      // construct with empty container, default comparator

  explicit priority_queue(const _Pr& _Pred)
    : c(), comp(_Pred)
  {}      // construct with empty container, specified comparator

  priority_queue(const _Pr& _Pred, const _Container& _Cont)
    : c(_Cont), comp(_Pred)
  {       // construct by copying specified container, comparator
    make_heap(c.begin(), c.end(), comp); 
  }

#pragma basic_template_matching
  template<class _Iter>
  priority_queue(_Iter _First, _Iter _Last)
    : c(_First, _Last), comp()
  {       // construct by copying [_First, _Last), default comparator
    make_heap(c.begin(), c.end(), comp); 
  }

#pragma basic_template_matching
  template<class _Iter>
  priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred)
    : c(_First, _Last), comp(_Pred)
  {       // construct by copying [_First, _Last), specified comparator
    make_heap(c.begin(), c.end(), comp); 
  }

#pragma basic_template_matching
  template<class _Iter>
  priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred,
                 const _Container& _Cont)
    : c(_Cont), comp(_Pred)
  {       // construct by copying [_First, _Last), container, and comparator
    c.insert(c.end(), _First, _Last);
    make_heap(c.begin(), c.end(), comp); 
  }

  bool empty() const
  {       // test if queue is empty
    return (c.empty()); 
  }

  size_type size() const
  {       // return length of queue
    return (c.size()); 
  }

  const value_type& top() const
  {       // return highest-priority element
    return (c.front()); 
  }

  value_type& top()
  {       // return mutable highest-priority element (retained)
    return (c.front()); 
  }

  void push(_ParamTy _Pred)
  {       // insert value in priority order
    c.push_back(_Pred);
    push_heap(c.begin(), c.end(), comp); 
  }

  void pop()
  {       // erase highest-priority element
    pop_heap(c.begin(), c.end(), comp);
    c.pop_back(); 
  }

protected:
  _Container c;   // the underlying container
  _Pr comp;       // the comparator functor
};
#pragma language = restore
_STD_END
#endif /* _QUEUE_ */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 V5.04:0576 */
